class Solution {
public:
    int countArrangement(int n) {
       int mask = 1 << n;
       vector<vector<int>>dp(n + 1, vector<int>(mask));
       dp[0][0] = 1;
       for(int i = 1; i <= n; i++){
           for(int j = 0; j < mask; j++){
               for(int k = 1; k <= n; k++){
                   if(!(1 & (j >> (k - 1))))continue;
                   if((k % i) && (i % k))continue;
                   dp[i][j] += dp[i - 1][j ^ (1 << (k - 1))];
               }
           }
       }
       return dp[n][mask - 1];
    }
};

/**
 * 2021.8.16
 * 状压DP
 * dp[i][j] 表示 取 j二进制位为 1 的那些数字来填满 前 i 个位置的方案数
 */